{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #反转链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定单链表的头节点 <code>head</code> ，请反转链表，并返回反转后的链表的头节点。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg\" style=\"width: 302px; \" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5]\n",
    "<strong>输出：</strong>[5,4,3,2,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg\" style=\"width: 102px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2]\n",
    "<strong>输出：</strong>[2,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目范围是 <code>[0, 5000]</code></li>\n",
    "\t<li><code>-5000 &lt;= Node.val &lt;= 5000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？</p>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 206&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/reverse-linked-list/\">https://leetcode-cn.com/problems/reverse-linked-list/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [UHnkqh](https://leetcode.cn/problems/UHnkqh/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [UHnkqh](https://leetcode.cn/problems/UHnkqh/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[1,2]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        p_head = head\n",
    "        p_tail = head\n",
    "        if p_tail is None:\n",
    "            return head\n",
    "        while p_tail.next is not None:\n",
    "            temp = p_tail.next\n",
    "            p_tail.next = temp.next\n",
    "            temp.next = p_head\n",
    "            p_head = temp\n",
    "        return p_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # pre  利用当前节点head连接pre\n",
    "        #为防止下一节点丢失，故在head连接时利用next1指向下一节点\n",
    "        #并在head连接后，将下一节点赋值给head\n",
    "        pre = None\n",
    "        while head :\n",
    "            #备用节点\n",
    "            next1 = head.next\n",
    "\n",
    "            head.next = pre\n",
    "\n",
    "            pre, head = head, next1\n",
    "        return pre\n",
    "    \n",
    "            \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        slow,fast = None, head\n",
    "        while fast:\n",
    "            temp = fast.next\n",
    "            fast.next = slow\n",
    "            slow = fast\n",
    "            fast = temp\n",
    "        return slow\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        cur = head\n",
    "        m = cur.next\n",
    "        cur.next = None\n",
    "        while m:\n",
    "            n=m.next\n",
    "            m.next=cur\n",
    "            cur = m\n",
    "            m = n\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        cur, pre = head,None\n",
    "        while cur:\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        cur, pre = head, None\n",
    "        while cur:\n",
    "            tmp = cur.next # 暂存后继节点 cur.next\n",
    "            cur.next = pre # 修改 next 引用指向\n",
    "            pre = cur      # pre 暂存 cur\n",
    "            cur = tmp      # cur 访问下一节点\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        q = deque()\n",
    "        p = head\n",
    "        while p:\n",
    "            q.append(p.val)\n",
    "            p = p.next\n",
    "        p = head\n",
    "        while p:\n",
    "            p.val = q[-1]\n",
    "            q.pop()\n",
    "            p = p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        root,pre = head,None\n",
    "        while root is not None:\n",
    "            nt = root.next \n",
    "            root.next = pre \n",
    "            pre = root \n",
    "            root = nt \n",
    "\n",
    "        return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        while cur != None:\n",
    "            tmp1 = cur.next\n",
    "            cur.next = pre\n",
    "            pre, cur = cur, tmp1\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            print(cur.val)\n",
    "            next_node = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = next_node\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        rest = None\n",
    "        while head is not None:\n",
    "            new_node = ListNode(head.val,rest)\n",
    "            rest = new_node\n",
    "            head = head.next\n",
    "        return rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # 长度为0，或者长度为1，不需要翻转\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        # 长度>=2，开始翻转\n",
    "        # last = head # 不能直接等号，这是个引用，会出错\n",
    "        last = ListNode(val=head.val)\n",
    "        tmp = head.next\n",
    "        while tmp.next:\n",
    "            # 创建一个新的节点吧\n",
    "            tmp_new = ListNode(val=tmp.val, next=last)\n",
    "            last = tmp_new\n",
    "            tmp = tmp.next\n",
    "        tmp.next = last\n",
    "        return tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # # 方法1：双指针法\n",
    "        # pre, cur = None, head\n",
    "        # while cur:\n",
    "        #     tmp = cur.next\n",
    "        #     cur.next = pre\n",
    "        #     pre = cur\n",
    "        #     cur = tmp\n",
    "        # return pre\n",
    "\n",
    "        # 借助列表法\n",
    "        lst, cur, pre = [], head, None\n",
    "        while cur:\n",
    "            lst.append(cur.val)\n",
    "            cur = cur.next\n",
    "        lst = lst[::-1]\n",
    "        for i in range(len(lst) - 1, -1, -1):\n",
    "            curnode = ListNode(lst[i])\n",
    "            curnode.next = pre\n",
    "            pre = curnode\n",
    "        return pre\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        new_head = None\n",
    "        while head:\n",
    "            new_head = ListNode(head.val, new_head)\n",
    "            head = head.next\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        cur = head\n",
    "        if not head:\n",
    "            return head\n",
    "        li = []\n",
    "        while cur:\n",
    "            li.append(cur.val)\n",
    "            cur = cur.next\n",
    "        li = li[::-1]\n",
    "        new_head = pre = ListNode(li[0])\n",
    "        for _ in li[1:]:\n",
    "            node = ListNode(_)\n",
    "            pre.next = node\n",
    "            pre = node\n",
    "        return new_head\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        if head:\n",
    "            cur=head\n",
    "            list1=[]\n",
    "            while cur:\n",
    "                list1.append(cur.val)\n",
    "                cur=cur.next\n",
    "            list1=list1[::-1]\n",
    "            head1=ListNode(list1[0])\n",
    "            cur1=head1\n",
    "            for i in list1[1:]:\n",
    "                cur1.next=ListNode(i)\n",
    "                cur1=cur1.next\n",
    "            return head1\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head:return head\n",
    "        stack = []\n",
    "        while head:\n",
    "            stack.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "\n",
    "        dummy = ListNode(0)\n",
    "        cur = dummy\n",
    "        while stack:\n",
    "            cur.next = ListNode(stack.pop())\n",
    "            cur = cur.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # cur = ListNode()\n",
    "        cur = dummy = ListNode()\n",
    "        if head:\n",
    "            # cur = dummy = ListNode(head.val)\n",
    "            cur = ListNode(head.val)\n",
    "            print(cur.val)\n",
    "            head = head.next\n",
    "            if not head: return cur\n",
    "            # return dummy\n",
    "        else: return None\n",
    "        while head:\n",
    "            # next_ = ListNode(head.val)\n",
    "            # cur = next_.next\n",
    "            # cur = next_\n",
    "            next_ = ListNode(head.val)\n",
    "            next_.next = cur\n",
    "            cur = next_\n",
    "            print(cur.val)\n",
    "            head = head.next\n",
    "            # return dummy\n",
    "        return next_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        res_ls = []\n",
    "\n",
    "        while head:\n",
    "            res_ls.append(head.val)\n",
    "            head = head.next\n",
    "\n",
    "        # print(res_ls)\n",
    "        res = cur = ListNode()\n",
    "        while res_ls:\n",
    "            cur.next = ListNode(res_ls.pop(-1))\n",
    "            # print(res_ls)\n",
    "            # print(res.next)\n",
    "            cur = cur.next\n",
    "\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "\n",
    "        if head and not head.next:\n",
    "            return head\n",
    "\n",
    "        last = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "            if head == None:\n",
    "                return None\n",
    "            if head.next==None:\n",
    "                return head\n",
    "\n",
    "            \n",
    "            now_head = self.reverseList(head.next)\n",
    "            head.next.next = head\n",
    "            head.next=None\n",
    "\n",
    "            return now_head\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "\n",
    "        if head and not head.next:\n",
    "            return head\n",
    "\n",
    "        last = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        cur = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        last = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # #迭代\n",
    "        # pre=None\n",
    "        # cur=head\n",
    "        # while cur:\n",
    "        #     next=cur.next\n",
    "        #     cur.next=pre\n",
    "        #     pre=cur\n",
    "        #     cur=next\n",
    "        # return pre\n",
    "\n",
    "        #递归\n",
    "        if not head or not head.next:return head\n",
    "        newhead=self.reverseList(head.next)\n",
    "        b=head.next\n",
    "        b.next=head\n",
    "        head.next=None\n",
    "        return newhead\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:return head\n",
    "        newHead = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return newHead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        \n",
    "        newHead = Solution().reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return newHead\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        \"\"\"\n",
    "        思路：链表反转，这个题目很简单，但也是面试中会容易遇到的问题。可以通过递归的方法，也可以通过迭代的方式。\n",
    "        \"\"\"\n",
    "        # 方法1. 递归的思路\n",
    "        if not head or not head.next:  return head\n",
    "        p = self.reverseList(head.next)  # 其实此处递归就是分治思路的体现\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return p\n",
    "        \n",
    "        # 方法2. 迭代的思路\n",
    "        # 迭代的方式，其实是通过三个指针来实现的，真的很简单的。\n",
    "        prev, curr = None, head   # 初始时分别指向None和head\n",
    "        while curr:  # 移动指针\n",
    "            next_p = curr.next  # 保存当前指针的下一个指针\n",
    "            curr.next = prev  # 然后让当前指针反过来指向prev\n",
    "\n",
    "            prev = curr    # 接着再让prev移动当curr的位置上\n",
    "            curr = next_p    # 然后curr移动到下一个位置上，这样就让prev,curr均顺序向后移动了。\n",
    "\n",
    "        return prev   # 最后prev会移动到最后一个元素上，返回其作为头指针即可完成链表的反转"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        new_head = ListNode(0)\n",
    "        tmp = self.reverseList(head.next)\n",
    "        new_head.next = tmp\n",
    "        while tmp.next:\n",
    "            tmp = tmp.next\n",
    "        tmp.next = head\n",
    "        head.next = None\n",
    "        return new_head.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        p=self.reverseList(head.next)\n",
    "        head.next.next=head\n",
    "        head.next=None\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "def reverseListPro(head):\n",
    "        if head == None or head.next == None:\n",
    "            return head\n",
    "        new = reverseListPro(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return new\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        return reverseListPro(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        def reverse(head):\n",
    "            if head is None or head.next is None:\n",
    "                return head\n",
    "            new_head = reverse(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return new_head\n",
    "        return reverse(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "                          \n",
    "        # 法二：递归法\n",
    "        def reverse(cur, pre):\n",
    "            if not cur: return pre\n",
    "            res = reverse(cur.next, cur)\n",
    "            cur.next = pre\n",
    "            return res\n",
    "        return reverse(head, None)\n",
    "                          \n",
    "        if not head or not head.next: return head\n",
    "                          \n",
    "        pre = None\n",
    "        cur = head\n",
    "\n",
    "        while cur:\n",
    "            post = cur.next\n",
    "            cur.next = pre\n",
    "\n",
    "            pre = cur\n",
    "            cur = post\n",
    "\n",
    "        return  pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head: return None\n",
    "\n",
    "        def dfs(node: ListNode):\n",
    "            if not node.next: return node\n",
    "\n",
    "            newHead = dfs(node.next)\n",
    "\n",
    "            node.next.next = node\n",
    "            node.next = None\n",
    "\n",
    "            return newHead\n",
    "        \n",
    "        \n",
    "        return dfs(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        if not head.next:\n",
    "            return head\n",
    "        headNode = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return headNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # prev,cur = None, head\n",
    "        # while cur:\n",
    "        #     next_n = cur.next\n",
    "        #     cur.next = prev\n",
    "        #     prev = cur\n",
    "        #     cur = next_n\n",
    "        # return prev  \n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        newHead = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return newHead\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # pre,cur = None,head\n",
    "        # while cur:\n",
    "        #     tmp = cur.next\n",
    "        #     cur.next = pre\n",
    "        #     pre = cur\n",
    "        #     cur = tmp\n",
    "        # return pre\n",
    "        def recur(cur,pre):\n",
    "            if not cur:\n",
    "                return pre\n",
    "            res = recur(cur.next,cur)\n",
    "            cur.next = pre\n",
    "            return res\n",
    "        return recur(head,None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # pre,cur = None,head\n",
    "        # while cur:\n",
    "        #     tmp = cur.next\n",
    "        #     cur.next = pre\n",
    "        #     pre = cur\n",
    "        #     cur = tmp\n",
    "        # return pre\n",
    "        def recur(cur,pre):\n",
    "            if not cur:\n",
    "                return pre\n",
    "            res = recur(cur.next,cur)\n",
    "            cur.next = pre\n",
    "            return res\n",
    "        return recur(head,None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "\n",
    "        ans = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        pre = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        stack=[]\n",
    "        if head==None or head.next==None:\n",
    "            return head\n",
    "        cur=head\n",
    "        pre=ListNode(0)\n",
    "        pre.next=cur\n",
    "        while(cur.next!=None):\n",
    "            cur=cur.next\n",
    "            pre=pre.next\n",
    "        pre.next=None\n",
    "        cur.next=self.reverseList(head)\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        stack=[]\n",
    "        if head==None or head.next==None:\n",
    "            return head\n",
    "        cur=head\n",
    "        pre=ListNode(0)\n",
    "        pre.next=cur\n",
    "        while(cur.next!=None):\n",
    "            cur=cur.next\n",
    "            pre=pre.next\n",
    "        pre.next=None\n",
    "        cur.next=self.reverseList(head)\n",
    "        return cur\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        def reverse(temp_head,reshead):\n",
    "            if temp_head is None: return reshead\n",
    "            insert_node = ListNode(val=temp_head.val,next=reshead.next)\n",
    "            reshead.next = insert_node\n",
    "            reverse(temp_head.next,reshead)\n",
    "\n",
    "            return reshead\n",
    "        reshead = ListNode()\n",
    "        reverse(head,reshead)\n",
    "        return reshead.next\n",
    "\n",
    "\n",
    "        # 赋值 迭代\n",
    "        # temp_head = ListNode()\n",
    "        # while head is not None:\n",
    "        #     insert_node = ListNode(val=head.val,next=temp_head.next)\n",
    "        #     temp_head.next = insert_node\n",
    "        #     head=head.next\n",
    "        # return temp_head.next\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        def solve(ans,l):\n",
    "            if l==None:\n",
    "                return ans\n",
    "            return solve(ListNode(l.val,ans),l.next)\n",
    "        if not head:\n",
    "            return head\n",
    "        return solve(ListNode(head.val,None),head.next)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        middle = ListNode()\n",
    "        if head is None :\n",
    "            return head\n",
    "        elif head.next is None:\n",
    "            return head\n",
    "        else:\n",
    "            middle = self.reverseList(head.next)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "            return middle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        def reverse(targe1t, temp):\n",
    "            if targe1t is not None:\n",
    "                temp1 = ListNode(targe1t.val)\n",
    "                temp1.next = temp\n",
    "                return reverse(targe1t.next, temp1)\n",
    "            else:\n",
    "                return temp\n",
    "        return reverse(head, None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "        res = None\n",
    "        def revList(root):\n",
    "            tmp = ListNode()\n",
    "            tmp.val = root.val\n",
    "            if not root.next:\n",
    "                nonlocal res \n",
    "                res = tmp\n",
    "                return tmp\n",
    "            else:\n",
    "                r = revList(root.next)\n",
    "                r.next = tmp\n",
    "                r = r.next\n",
    "                return r\n",
    "\n",
    "        revList(head)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        # 如果传入的列表为空，或者到了最后一个结点\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        # 反转以head.next为头结点的单链表\n",
    "        new_head = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        the_last = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return the_last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next: return head\n",
    "        node=self.reverseList(head.next)\n",
    "        head.next.next=head\n",
    "        head.next=None\n",
    "        return node\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        reversalHead = self.reverseList(head.next)\n",
    "        head.next.next = head\n",
    "        head.next = None\n",
    "        return reversalHead\n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        ans = None\n",
    "        def reverse(ans, first):\n",
    "            if not first or first and first.next == None:\n",
    "                ans = first\n",
    "                return ans, first\n",
    "            ans, tail = reverse(ans,first.next)\n",
    "            tail.next = first\n",
    "            first.next = None\n",
    "            return ans, first\n",
    "\n",
    "        ans, _ = reverse(ans,head)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        self.ans = None\n",
    "        def dfs(pre, root):\n",
    "            if not root:\n",
    "                return\n",
    "            if not root.next:\n",
    "                self.ans = root\n",
    "            dfs(root, root.next)\n",
    "            root.next = pre\n",
    "            if pre:\n",
    "                pre.next = None\n",
    "            \n",
    "        dfs(None, head)\n",
    "        return self.ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
